import { checkSortFunction } from "./testCase.js";

const exchange = (arr, i, j) => {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

const bubbingSort = (arr) => {
    const l = arr.length;
    if (l < 2) return arr;
    for (let i = 0; i < l; i++) {
        for (let j = 0; j < l - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                exchange(arr, j, j + 1);
            }
        }
    }
    return arr;
}

const chooseSort = (arr) => {
    const l = arr.length;
    if (l < 2) return arr;
    for (let i = 0; i < l; i++) {
        let maxNum = arr[0], maxIndex = 0;
        for (let j = 1; j < l - i; j++) {
            if (arr[j] > maxNum) {
                maxNum = arr[j];
                maxIndex = j;
            }
        }
        exchange(arr, maxIndex, l - i - 1);
    }
    return arr;
}

const insertSort = (arr) => {
    const l = arr.length;
    if (l < 2) return arr;
    const res = [arr[0]];
    for (let i = 0; i < l; i++) {
        const cur = arr[i];
        for (let j = 0; j < i; j++) {
            if (cur < res[j]) {
                res.splice(j, 0, cur);
                break;
            }
        }
    }
    return arr
}

const fastSort = (arr) => {
    const l = arr.length;
    if (l < 2) return arr;

    const middileIndex = Math.floor(l / 2);
    const leftArr = arr.slice(0, middileIndex);
    const rightArr = arr.slice(middileIndex);

    return [...fastSort(leftArr), arr[middileIndex], ...fastSort(rightArr)];
}

const mergeSort = (arr) => {
    const l = arr.length;
    if (l < 2) return arr;

    const middileIndex = Math.floor(l / 2);
    const leftArr = arr.slice(0, middileIndex);
    const rightArr = arr.slice(middileIndex);

    const merge = (left = [], right = []) => {
        const result = [];
        let leftIndex = 0, rightIndex = 0;
        while(leftIndex < left.length && rightIndex < right.length) {
            if (left[leftIndex] < right[rightIndex]) {
                result.push(left[leftIndex]);
                leftIndex++;
            } else {
                result.push(right[rightIndex]);
                rightIndex++;
            }
        }
        return result
    }

    return merge(mergeSort(leftArr), ...mergeSort(rightArr));
}

[bubbingSort, chooseSort, insertSort, fastSort, mergeSort].forEach((func) => {
    checkSortFunction(func);
})


export {
    bubbingSort,
    chooseSort,
    insertSort,
    fastSort,
    mergeSort,
}